package tree.structure.rbtree;

import java.util.Arrays;

/**
 * @author: 26233
 * @create: 2022-07-26 17:09:28
 * @Description
 *
 * 红黑树插入时的调整：
 *      插入的节点颜色默认是红色，因此会出现连续的红节点而破坏红黑树的基本性质，导致需要调整树结构或者节点的颜色
 *      1. 先调色：如果父节点存在，且父节点的兄弟节点存在并且为红节点，则直接将父节点和父节点的兄弟节点颜色置为黑，并递归到根节点，完成调整。此时左右子树的黑高度不会发生改变。
 *      2. 不能直接调色，则需要先旋转，然后再调色
 *          a. 旋转按照avl树的规则，LR,RL,LL,RR
 *          b. 旋转之后的子节点(调整时候的主要节点)置红，父节点(一般是红的)置黑，完成调整
 *      // 直接调色和旋转后的调色是为了保证左右子树的黑高度能保持相等(比如说：旋转之后的子节点有黑有红，那么直接把子节点变红，并把
 *      父节点变黑，其实左右子树的黑高度刚好是保持相同，因为只是改变了路径上的黑节点而已即自己变红了，但父节点是黑的，所以黑高度会保持和原来相等)
 *
 *  红黑树删除时的调整：
 *      为了简化删除操作，一般不直接对删除节点做处理，而是将删除节点的后继节点替换上来，然后删除后继节点，一般后继节点在叶子上或者不存在左子树
 *      所以操作都是在替换节点（后继节点）上
 *      1. 如果替换节点是红色，则可以不做处理，因为不影响黑高度
 *      2. 如果替换节点是黑色（分左子节点和右子节点）
 *          a. 替换节点的兄弟节点是红色
 *              则根据性质，替换节点的父亲节点一定是黑色，兄弟节点的儿子一定是黑色
 *              此时删除后，右子树黑高度会减一，所以进行右旋操作，并将父节点置红。（旋转操作将右子树的黑高度减一，使左右子树黑高度保持一致）
 *          b. 替换节点的兄弟节点是黑色
 *              此时考虑兄弟节点的子节点颜色并进行相应的旋转，变色操作
 *
 *
 **/

public class RBTree {

    static boolean BLACK = false;
    static boolean RED = true;

    private RBNode root;
    private int height;

    // 插入新节点
    public void insert(RBNode newNode){
        // 情景1：空树
        if (root == null){
            root = newNode;
            root.setRed(BLACK);
            return;
        }
        RBNode insertParentNode = setChild(newNode, root);
        assert insertParentNode != null;

        // 情景3：父节点为黑节点
        if(!insertParentNode.isRed()){
            return;
        }
        // 情景4
        adjust(newNode);
    }

    // 调整树结构
    public void adjust(RBNode newNode){

        if (newNode == root){
            root.setRed(BLACK);
            return;
        }

        if(!(newNode.isRed() && newNode.getParent().isRed())){
            return;
        }

        RBNode parent = newNode.getParent();
        RBNode pParent = parent.getParent();

        int pLeft = isLeft(newNode, parent);
        int pPLeft = isLeft(parent, pParent);

        if (pPLeft == 0){
            // 情景4.1
            if(pParent.getRight() != null) {
                if (pParent.getRight().isRed()){
                    parent.setRed(BLACK);
                    pParent.getRight().setRed(BLACK);
                    pParent.setRed(RED);
                    // 递归修改
                    adjust(pParent);
                    return;
                }
                else {// parent的兄弟节点是黑节点
                     }
            }
            else {// 右儿子为空
                 }
            if (pLeft == 0){ // 情景4.2.1 LL
                parent.setParent(pParent.getParent());
                pParent.setParent(parent);
                pParent.setLeft(null);
                parent.setRight(pParent);

                pParent.setRed(RED);
                parent.setRed(BLACK);

                if (parent.getParent() == null) {
                    root = parent;
                }else {
                    if (parent.getParent().getLeft() == parent.getRight()){
                        parent.getParent().setLeft(parent);
                    }else {
                        parent.getParent().setRight(parent);
                    }
                }
                // 递归
                adjust(parent);
            }else {// 情景4.2.2 LR
                newNode.setParent(pParent.getParent());
                parent.setParent(newNode);
                pParent.setParent(newNode);
                pParent.setLeft(null);
                parent.setRight(null);

                newNode.setLeft(parent);
                newNode.setRight(pParent);

                pParent.setRed(RED);
                newNode.setRed(BLACK);

                if (newNode.getParent() == null) {
                    root = parent;
                }else {
                    if (newNode.getParent().getLeft() == newNode.getRight()){
                        newNode.getParent().setLeft(newNode);
                    }else {
                        newNode.getParent().setRight(newNode);
                    }
                }
                // 递归
                adjust(newNode);
            }
        }else {
            // 情景4.1
            if(pParent.getLeft() != null) {
                if (pParent.getLeft().isRed()){
                    parent.setRed(BLACK);
                    pParent.getLeft().setRed(BLACK);
                    pParent.setRed(RED);
                    // 递归修改
                    adjust(pParent);
                    return;
                }else {// parent的兄弟节点是黑节点
                }
            }else {
            }
            if (pLeft == 0){ // 情景4.3.1 RL
                newNode.setParent(pParent.getParent());
                parent.setParent(newNode);
                pParent.setParent(newNode);

                newNode.setRight(parent);
                newNode.setLeft(pParent);

                pParent.setRed(RED);
                if (newNode.getParent() == null) {
                    root = parent;
                }else {
                    if (newNode.getParent().getLeft() == newNode.getLeft()){
                        newNode.getParent().setLeft(newNode);
                    }else {
                        newNode.getParent().setRight(newNode);
                    }
                }
                // 递归
                adjust(newNode);
            }else {// 情景4.3.2 RR
                parent.setParent(pParent.getParent());
                pParent.setParent(parent);
                pParent.setRight(parent.getLeft());
                parent.setLeft(pParent);

                pParent.setRed(RED);

                if (parent.getParent() == null) {
                    root = parent;
                }else {
                    if (parent.getParent().getLeft() == parent.getRight()){
                        parent.getParent().setLeft(parent);
                    }else {
                        parent.getParent().setRight(parent);
                    }
                }
                // 递归
                adjust(parent);
            }
        }
    }

    public int isLeft(RBNode child, RBNode parent){
        return parent.getLeft() == child ? 0 : 1;
    }

    public RBNode setChild(RBNode newNode, RBNode root) {
        RBNode tempRoot = root;
        RBNode returnNode;
        if(newNode.getV() <= tempRoot.getV()) {
            if (tempRoot.getLeft() == null){
                tempRoot.setLeft(newNode);
                newNode.setParent(tempRoot);
                return tempRoot;
            }else {
                tempRoot = tempRoot.getLeft();
                returnNode = setChild(newNode, tempRoot);
            }
        }else {
            if (tempRoot.getRight() == null){
                tempRoot.setRight(newNode);
                newNode.setParent(tempRoot);
                return tempRoot;
            }else {
                tempRoot = tempRoot.getRight();
                returnNode = setChild(newNode, tempRoot);
            }
        }
        return returnNode;
    }

    public RBNode getRoot() {
        return root;
    }


    public static void main(String[] args) {

        int[] data = new int[]{2, 3, 10, 5, 4, 7, 8, 1, 9};
        RBTree rbTree = new RBTree();
        Arrays.stream(data).forEach(v -> rbTree.insert(new RBNode(v)));

        System.out.println();

    }

}
